The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Relational database management systems store information in tables, where each piece of data is stored at a particular row and column. Information in a given row generally is associated with a particular object, and information in a given column generally relates to a particular category of information. For example, each row of a table may correspond to a particular employee, and the various columns of the table may correspond to employee names, employee social security numbers, and employee salaries.
A user retrieves information from and submits updates to a database by interacting with a database application. The user's actions are converted into a query by the database application. The database application submits the query to a database server. The database server responds to the query by accessing the tables specified in the query to determine which information stored in the tables satisfies the queries. The information that satisfies the queries is retrieved by the database server and transmitted to the database application. Alternatively, a user may request information directly from the database server by constructing and submitting a query directly to the database server using a command line or graphical interface.
Queries submitted to the database server must conform to the rules of a particular query language. One popular query language, known as the Structured Query Language (SQL), provides users a variety of ways to specify information to be retrieved. In SQL and other query languages, queries may include inner query blocks. For example, the query
SELECT T1.xFROM table1 T1, parts PWHERE P.y = T1.y AND P.z = ‘MED BOX’AND T1 .quantity < (SELECT AVG (T2.quantity)FROM Table2 T2WHERE T2.partkey = P.partkey)AND P.quantity < (SELECT AVG (T3.quantity)FROM Table3 T3WHERE T3.serialnum = T1.serialnum);has one outer query block and two inner query blocks, and each inner query block is a subquery:                SELECT AVG (T2.quantity) FROM Table2 T2 WHERE T2.partkey=P.partkey and        SELECT AVG (T3.quantity) FROM Table3 T3 WHERE T3.serialnum=T1.serialnum.        
In one approach to processing queries, the original queries are executed or stored for later execution. A problem with this approach is that there may be more efficient ways of determining the results than executing the query as it was received.
In a second approach, a received query is transformed based on heuristics. The transformed version of the query is then executed in place of the original query. Since the transformed query is semantically equivalent to the original query, the same results are produced. However, since the transformed query typically has a lower cost than the original query, the same results are obtained with less computational cost than would have been incurred if the original query were executed. A problem with this approach, however, is that, even though a semantically equivalent query with a lower-cost than the original query may have been produced via the transformations, there still may be more efficient ways of determining the results than executing the transformed query.
Based on the discussion above, there is clearly a need for techniques that overcome the shortfalls of previous approaches.